package array.SpiralArray;

import java.util.ArrayList;
import java.util.List;

/**
 * 题目:给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
       示例:输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
           输出：[1,2,3,6,9,8,7,4,5]

 * 思路与59.螺旋矩阵II不同的是：前题中的螺旋矩阵是正方形，只有正方形的边长n一个边界条件，
       而本题中，需要考虑长方形的长和宽(m行和n列)两个边界条件。自然，m可以等于n，即前题可视为本题在m==n的特殊情况。

 * m和n的带入，主要引来两方面的差异：
   loop的计算：
    本题的loop计算与59.螺旋矩阵II算法略微差异，因为存在rows和columns两个维度，可自行分析，loop只能取min(rows, columns)，
    例如rows = 5, columns = 7，那loop = 5 / 7 = 2
   mid的计算及填充：
    1、同样的原理，本题的mid计算也存在上述差异；
    2、
    如果min(rows, columns)为偶数，则不需要在最后单独考虑矩阵最中间位置的赋值
    如果min(rows, columns)为奇数，则矩阵最中间位置不只是[mid][mid],而是会留下来一个特殊的中间行或者中间列，
   具体是中间行还是中间列，要看rows和columns的大小，如果rows > columns,则是中间列，相反，则是中间行
 */
public class matrixArray {
    public List<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> list = new ArrayList<>();
        int m = matrix[0].length;  // 矩阵的列数
        int n = matrix.length;     // 矩阵的行数
        int startx = 0, starty = 0; // 当前螺旋层的起始坐标
        int loop = Math.min(m, n) / 2; // 完整螺旋的圈数（每圈包含四边）
        int mid = loop;             // 中间位置（用于处理剩余部分）
        int offset = 1;            // 边界偏移量（控制每圈大小）

        // 遍历完整螺旋圈（每次处理一层）
        while (loop > 0) {
            // 1. 从左到右遍历上边 (左闭右开)
            int j = starty;
            for (; j < m - offset; j++) {
                list.add(matrix[startx][j]);
            }

            // 2. 从上到下遍历右边 (上闭下开)
            int i = startx;
            for (; i < n - offset; i++) {
                list.add(matrix[i][j]); // 注意：j此时位于最右侧列
            }

            // 3. 从右到左遍历下边 (右闭左开)
            for (; j > starty; j--) {
                list.add(matrix[i][j]); // 注意：i此时位于最下方行
            }

            // 4. 从下到上遍历左边 (下闭上开)
            for (; i > startx; i--) {
                list.add(matrix[i][j]); // 注意：j此时位于最左侧列
            }

            // 调整内层参数：
            startx++; // 起始行下移
            starty++; // 起始列右移
            offset++; // 边界收缩
            loop--;   // 剩余圈数减1
        }

        // 处理中心剩余部分（当 min(m,n) 为奇数时）
        if (Math.min(m, n) % 2 != 0) {
            if (m > n) {
                // 剩余水平条带（一行）：从 mid 列开始向右延伸
                for (int j = mid; j < mid + m - n + 1; j++) {
                    list.add(matrix[mid][j]); // mid 即当前中心行
                }
            } else {
                // 剩余垂直条带（一列）：从 mid 行开始向下延伸
                for (int i = mid; i < mid + n - m + 1; i++) {
                    list.add(matrix[i][mid]); // mid 即当前中心列
                }
            }
        }
        return list;
    }
}
